home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / p_sweep.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  3KB  |  179 lines
  1. #include <LEDA/plane.h>
  2. #include <LEDA/window.h>
  3. #include <LEDA/prio.h>
  4. #include <LEDA/sortseq.h>
  5. #include <LEDA/p_dictionary.h>
  6.  
  7. #include <math.h>
  8.  
  9.  
  10. static double X_POS;
  11.  
  12.  
  13. int compare(segment& s1,segment& s2)
  14. {
  15.   line l1(s1);
  16.   line l2(s2);
  17.  
  18.   double diff = l1.y_proj(X_POS) - l2.y_proj(X_POS);
  19.  
  20.   if (fabs(diff) < 1e-10)
  21.      return compare(l1.slope(),l2.slope());
  22.   else 
  23.      return compare(diff,0.0);
  24. }
  25.  
  26. segment hor_seg(point p) { return segment(p,0,1); }
  27.  
  28.  
  29.  
  30. typedef priority_queue<segment,point> X_structure;
  31.  
  32.  
  33. typedef p_dictionary<segment,int> Y_structure; 
  34.  
  35.  
  36. typedef sortseq<double,Y_structure>  HISTORY;
  37.  
  38.  
  39. void sweep(list<segment>& L, HISTORY& H)
  40. {
  41.   X_structure    X;
  42.   Y_structure    Y;           
  43.   segment s;
  44.  
  45.   forall(s,L)                     // initialize the X_structure
  46.   { X.insert(s,s.start());
  47.     X.insert(s,s.end());
  48.    }
  49.  
  50.  
  51.   // start sweep
  52.  
  53.   X_POS = -MAXDOUBLE;         
  54.  
  55.   H.insert(X_POS,Y);              // insert empty Y_structure at -infinity
  56.  
  57.   while( !X.empty() )
  58.   {
  59.     pq_item it = X.find_min();
  60.     point   p = X.inf(it);        // p is the next transitition point
  61.     segment l = X.key(it);        // l is a segment starting or ending in p
  62.     X.del_item(it);
  63.  
  64.     X_POS = p.xcoord();           // move the sweep line to p
  65.  
  66.     if (l.start()==p)             // update Y_structure Y
  67.         Y = Y.insert(l,0);        // left point
  68.     else
  69.         Y = Y.del(l);             // rigth point
  70.  
  71.     H.insert(X_POS,Y);            // insert Y into history sequence 
  72.  
  73.   }
  74.  
  75.   H.insert(MAXDOUBLE,Y);          // insert empty Y_structure at +infinity
  76.   
  77. }
  78.  
  79.  
  80.  
  81.  
  82. segment locate(point p, HISTORY& H)
  83. {
  84.   X_POS = p.xcoord();
  85.  
  86.   Y_structure Y = H.inf(H.pred(X_POS));
  87.  
  88.   p_dic_item pit = Y.succ(hor_seg(p));
  89.  
  90.   if (pit != nil) 
  91.      return Y.key(pit);
  92.   else
  93.      return segment(0,0,0,0);
  94.   
  95. }
  96.  
  97.  
  98.  
  99. window W;
  100.  
  101. void draw_sweep_line()
  102. { int save = W.set_line_width(1);
  103.   W.draw_vline(X_POS,green);
  104.   W.set_line_width(save);
  105.  }
  106.  
  107. void draw_segment(segment s)
  108. { W.draw_segment(s,blue);
  109.  }
  110.  
  111. void show_segment(segment s)
  112. { draw_segment(s);
  113.   int save = W.set_line_width(5);
  114.   W.draw_segment(s,red);
  115.   W.set_line_width(save);
  116.  }
  117.  
  118. void hide_segment(segment s)
  119. { int save = W.set_line_width(5);
  120.   W.draw_segment(s,red);
  121.   W.set_line_width(save);
  122.   draw_segment(s);
  123.  }
  124.  
  125.  
  126. main()
  127. { 
  128.   HISTORY H;
  129.   segment s;
  130.   point p;
  131.  
  132.   list<segment> L;
  133.  
  134.   W.set_mode(xor_mode);
  135.   W.set_line_width(1);
  136.  
  137.   while (W >> s) 
  138.   { draw_segment(s);
  139.     L.append(s);
  140.    }
  141.  
  142.  sweep(L,H);
  143.  
  144.  
  145.  int key;
  146.  double x,y;
  147.  
  148.  X_POS = W.xmin();
  149.  L.clear();
  150.  
  151.  while ((key = W.read_mouse(x,y))!= 3 )  
  152.  {
  153.    forall(s,L) hide_segment(s);           
  154.    draw_sweep_line();
  155.    L.clear();
  156.  
  157.    switch(key) {
  158.  
  159.    case 1: L.append(locate(point(x,y),H));
  160.            X_POS = W.xmin();
  161.            break;
  162.  
  163.    case 2: { X_POS = x;
  164.              draw_sweep_line();
  165.              seq_item sit = H.pred(x);
  166.              Y_structure Y = H.inf(sit);
  167.              p_dic_item it;
  168.              forall_items(it,Y) L.append(Y.key(it));
  169.              break;
  170.             }
  171.    }
  172.  
  173.    forall(s,L) show_segment(s);           
  174.  
  175.   }
  176.   
  177.   return 0;
  178. }
  179.